package com.snap.vseries;

import java.util.Arrays;

public class Test {
    public static void main(String[] args) {
        int arr[] = new int[]{3, 4, 5, 6, 2, 1};
        System.out.println(Arrays.toString(arr));
        QuickSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }

    // 归并排序
//   public void MergeSort(int arr[], int start, int end, int temp) {
//        if (start >= end)
//            return;
//        int mid = (start + end) / 2;
//        MergeSort(arr, start, mid, temp);
//        MergeSort(arr, mid + 1, end, temp);
//
//        // 合并两个有序序列
//        int length = 0; // 表示辅助空间有多少个元素
//        int i_start = start;
//        int i_end = mid;
//        int j_start = mid + 1;
//        int j_end = end;
//        while (i_start <= i_end && j_start <= j_end) {
//            if (arr[i_start] < arr[j_start]) {
//                temp[length] = arr[i_start];
//                length++;
//                i_start++;
//            } else {
//                temp[length] = arr[j_start];
//                length++;
//                j_start++;
//            }
//        }
//        while (i_start <= i_end) {
//            temp[length] = arr[i_start];
//            i_start++;
//            length++;
//        }
//        while (j_start <= j_end) {
//            temp[length] = arr[j_start];
//            length++;
//            j_start++;
//        }
//        // 把辅助空间的数据放到原空间
//        for (int i = 0; i < length; i++) {
//            arr[start + i] = temp[i];
//        }
//    }
    // 快速排序
    public static void QuickSort(int arr[], int start, int end) {
        if (start >= end)
            return;
        int i = start;
        int j = end;
        // 基准数,以51 33 62 96 87 17 28 51为例，基准数为左起第一个，也就是51
        int baseVal = arr[start];
        //不停循环，直至i>=j
        while (i < j) {
            // 从后向前找比基准数小的数
            while (i < j && arr[j] >= baseVal) {
                j--;
            }
            //找到比基数小的数，把这个数移动到基数所在位置，相当于交换位置，虽然并没有arr[j]=baseVal;但是j这个位置相当于已经空出来了
            if (i < j) {
                arr[i] = arr[j];
                i++;
            }
            // 从前往后找比基准数大的数（上边i++的意思就是，刚刚那个小的不算）
            while (i < j && arr[i] < baseVal) {
                i++;
            }
            //找到比基数大的数，把这个数移动到基数所在位置（j）
            if (i < j) {
                arr[j] = arr[i];
                j--;
            }
        }
        // 把基准数放到i的位置
        arr[i] = baseVal;
        // 递归
        QuickSort(arr, start, i - 1);
        QuickSort(arr, i + 1, end);
    }

    // 插入排序，以4, 5,3, 6, 2, 1举例
    public static void InsertSort(int arr[], int length) {
        //从第一个的后一个开始，一趟插入一个
        for (int i = 1; i < length; i++) {
            int j;
            //如果后一个比前一个大就不需要处理，比如5
            // 如果后一个比前一个小,比如3,就把后一个插入到合适的位置
            if (arr[i] < arr[i - 1]) {
                //把后一个的值(3)临时赋给变量temp
                int temp = arr[i];
                //从3的前一个开始，到找到最后一个比3大的结束,只要比3大，就要向后移动一位
                for (j = i - 1; j >= 0 && temp < arr[j]; j--) {
                    arr[j + 1] = arr[j];
                }
                arr[j + 1] = temp;
            }
        }
        System.out.println(Arrays.toString(arr));
    }

    // 冒泡排序
    public static void BubbleSort(int arr[], int length) {
        //length趟比较
        for (int i = 0; i < length - 1; i++) {
            //第i趟，说明有i+1个大值已冒泡到最后，所以只要对length-(i+1)个值排序
            for (int j = 0; j < length - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j + 1];
                    arr[j + 1] = arr[j];
                    arr[j] = temp;
                }
            }
        }
        System.out.println(Arrays.toString(arr));
    }

    // 选择排序
    public static void SelectionSort(int arr[], int length) {
        //每趟都会找到一个最小的放在最前面，那么n个数排序，最多只需要n-1趟
        for (int i = 0; i < length - 1; i++) {
            //每趟都会找到一个最小的，默认最小的是第一个
            int index = i;
            //找到最小的
            for (int j = i + 1; j < length; j++) {
                if (arr[j] < arr[index]) {
                    index = j;
                }
            }
            //如果最小的是第一个，不做处理
            if (index == i)
                continue;
            else {
                //如果最小的不是第一个，和第一个交换位置
                int temp;
                temp = arr[index];
                arr[index] = arr[i];
                arr[i] = temp;
            }
        }
        System.out.println(Arrays.toString(arr));
    }


    /*
        @param arr 待调整的数组
        @param i 待调整的结点的下标
        @param length 数组的长度
    */
    void HeapAdjust(int arr[], int i, int length) {
        // 调整i位置的结点
        // 先保存当前结点的下标
        int max = i;
        // 当前结点左右孩子结点的下标
        int lchild = i * 2 + 1;
        int rchild = i * 2 + 2;
        if (lchild < length && arr[lchild] > arr[max]) {
            max = lchild;
        }
        if (rchild < length && arr[rchild] > arr[max]) {
            max = rchild;
        }
        // 若i处的值比其左右孩子结点的值小，就将其和最大值进行交换
        if (max != i) {
            int temp;
            temp = arr[i];
            arr[i] = arr[max];
            arr[max] = temp;
            // 递归
            HeapAdjust(arr, max, length);
        }
    }

    // 堆排序
    void HeapSort(int arr[], int length) {
        // 初始化堆
        // length / 2 - 1是二叉树中最后一个非叶子结点的序号
        for (int i = length / 2 - 1; i >= 0; i--) {
            HeapAdjust(arr, i, length);
        }
        // 交换堆顶元素和最后一个元素
        for (int i = length - 1; i >= 0; i--) {
            int temp;
            temp = arr[i];
            arr[i] = arr[0];
            arr[0] = temp;
            HeapAdjust(arr, 0, i);
        }
    }
}
